|
|
Výpočetní složitost v teorii grafů
Doucha, Martin ; Kratochvíl, Jan (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Tato práce zavádí dvě nové parametrizace grafových úloh zobecňující vrcholové pokrytí, které v hierarchii grafových parametrizací vyplňují část prostoru mezi vrcholovým pokrytím a klikovou šířkou. Dále zde zkoumáme parametrizovanou složitost hledání Hamiltonovské cesty a kružnice, klasického barvení grafu, problému Precoloring extension a Equitable coloring pro tyto nové parametrizace. Kromě problému Precoloring extension, který je pro jednu parametrizaci W[1]-těžký, se pro všechny ostatní problémy podařilo najít FPT algoritmus pro obě parametrizace. Hranici mezi třídami FPT a W[1] se tak u těchto problémů podařilo posunout blíže směrem k parametrizaci klikovou šířkou.
|
|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (vedoucí práce) ; Telle, Jan Arne (oponent) ; Obdržálek, Jan (oponent)
Název práce: Parametrizovaná složitost Autor: Ondřej Suchý Katedra (ústav): Katedra aplikované matematiky Školitel: Prof. RNDr. Jan Kratochvíl, CSc. e-mail školitele: honza@kam.mff.cuni.cz Abstrakt: Tato práce se zabývá parametrizovanou složitostí NP-těžkých grafo- vých problémů. Zkoumáme složitost problémů v různých scénářích, vzhle- dem k rozličným parametrům a jejich kombinacím. Naším cílem je spíše rozlišit v tomto mnohorozměrném smyslu, zda daný parametr dělá problém parametrizovaně dostupným, nebo nedostupným, než představit algorit- mus, který dosahuje nejlepší možné časové složitosti. V otázkách, které studujeme, je typicky parametr první volby neúspěšný a tak využíváme méně standardních parametrů. První zkoumaná množina problémů je společným zobecněním mnoha dobře známých a prostudovaných problémů dominance a nezávislosti. Navrhu- jeme zde použít duální parametrizaci a ukážeme, že narozdíl od standardní parametrizace velikostí řešení, tato parametrizace dokáže ohrančit nevyh- nutelnou kombinatorickou explozi. Další studované problémy jsou analogií Steinerova problému v orientovaných grafech. Parametrizace pomocí počtu terminalů se jeví jako dříve neprobádaná alternativa v...
|
|
|
Structural properties of graphs and eficient algorithms: Problems Between Parameters
Knop, Dušan ; Fiala, Jiří (vedoucí práce)
Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry Dušan Knop Parametrizovaná složitost se v přůběhu posledních dvou dekád stala jednou z nejvýznamějších oblastí výpočetní složitosti. Strukturální vlastnosti grafů (také nazývané grafové šířky) hrají dnes centrální roli jak v teorii grafů tak v návrhu (parametrizovaných) algoritmů. V těto práci za pomoci studia konkrétních problémů poukazujeme na souvislost strukturálních vlastností grafů a možnosti získání parametrizovaného algoritmu. Předvádíme proto parametrizované algo- ritmy a těžkostní redukce pro problémy Target Set Selection, Minimum Length Bounded Cut a další. Vstupem problému Minimum Length Bounded Cut je graf, dva jeho vrcholy (zdroj a stok) a kladné celé číslo L. Úkolem pak je naleznout minimální množinu hran po jejímž odebrání bude vzdálenost mezi zdrojem a stokem více než L. Ukazujeme, že je možné naleznout optimální řešení pro tento problém algoritmem s časem běhu f(k)n, kde f je vyčíslitelná funkce a k je tree-depth n vrcholového grafu na vstupu. Naopak takovýto algoritmus nemůže existovat pro parametr tree-width (pokud FPT ̸= W[1]). V současné době je jen velmi málo známých problémů s touto vlastností....
|
|
|
Variants of graph labeling problems
Masařík, Tomáš ; Fiala, Jiří (vedoucí práce) ; Fellows, Michael R. (oponent) ; Hell, Pavol (oponent)
Tato práce se skládá ze tří částí zasvědcených značkování grafů, dědičným grafovým třídám a parametrizované složitosti. Pakovací barvení, původně označované vysílací barevnost, přiřazuje vrcholům grafu přirozená čísla tak, že vrcholy se stejným číslem musí být od sebe vzdáleny alespoň o hodnotu danného čísla. Tento problém je motivován přiřazováním frekvencí vysílačům. My zlepšujeme těžkost na chordálních grafech. Dokazujeme, že pakovací barvení na chordálních grafech diametru 3 je velice těžké aproximovat. Navíc uvádíme několik pozitivních výsledků pro intervalové grafy a pro související strukturální grafové parametry. Dědičné grafové třídy jsou zachovány při mazání vrcholů. My studujeme grafy takové, které neobsahují podgraf H jako svůj indukovaný podgraf. Dokazujeme, že 3 barvení je polynomiálně řešitelné pro (P3 + P4)-free a (P2 + P5)-free grafy, a tudíž jsme vyřešili poslední otevřené případy pro H-free grafy, kde H má nanejvýš 7 vrcholů. Férové problémy jsou takové modifikace grafových mazacích problémů, kde místo minimalizace velikosti řešení, je cílem minimalizovat maximální počet sousedů ve smazané množině. My ukazujeme, že takové problémy jdou vyřešit ve FPT čase pro MSO1 formuli parametrizováno velikostí formule a twin pokrytím grafu. Navíc definujeme základní férový problém, férové...
|
|
|
Structural properties of graphs and eficient algorithms: Problems Between Parameters
Knop, Dušan ; Fiala, Jiří (vedoucí práce) ; Niedermeier, Rolf (oponent) ; Feldmann, Andreas Emil (oponent)
Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry Dušan Knop Parametrizovaná složitost se v přůběhu posledních dvou dekád stala jednou z nejvýznamějších oblastí výpočetní složitosti. Strukturální vlastnosti grafů (také nazývané grafové šířky) hrají dnes centrální roli jak v teorii grafů tak v návrhu (parametrizovaných) algoritmů. V těto práci za pomoci studia konkrétních problémů poukazujeme na souvislost strukturálních vlastností grafů a možnosti získání parametrizovaného algoritmu. Předvádíme proto parametrizované algo- ritmy a těžkostní redukce pro problémy Target Set Selection, Minimum Length Bounded Cut a další. Vstupem problému Minimum Length Bounded Cut je graf, dva jeho vrcholy (zdroj a stok) a kladné celé číslo L. Úkolem pak je naleznout minimální množinu hran po jejímž odebrání bude vzdálenost mezi zdrojem a stokem více než L. Ukazujeme, že je možné naleznout optimální řešení pro tento problém algoritmem s časem běhu f(k)n, kde f je vyčíslitelná funkce a k je tree-depth n vrcholového grafu na vstupu. Naopak takovýto algoritmus nemůže existovat pro parametr tree-width (pokud FPT ̸= W[1]). V současné době je jen velmi málo známých problémů s touto vlastností....
|
|
|
Structural properties of graphs and eficient algorithms: Problems Between Parameters
Knop, Dušan ; Fiala, Jiří (vedoucí práce)
Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry Dušan Knop Parametrizovaná složitost se v přůběhu posledních dvou dekád stala jednou z nejvýznamějších oblastí výpočetní složitosti. Strukturální vlastnosti grafů (také nazývané grafové šířky) hrají dnes centrální roli jak v teorii grafů tak v návrhu (parametrizovaných) algoritmů. V těto práci za pomoci studia konkrétních problémů poukazujeme na souvislost strukturálních vlastností grafů a možnosti získání parametrizovaného algoritmu. Předvádíme proto parametrizované algo- ritmy a těžkostní redukce pro problémy Target Set Selection, Minimum Length Bounded Cut a další. Vstupem problému Minimum Length Bounded Cut je graf, dva jeho vrcholy (zdroj a stok) a kladné celé číslo L. Úkolem pak je naleznout minimální množinu hran po jejímž odebrání bude vzdálenost mezi zdrojem a stokem více než L. Ukazujeme, že je možné naleznout optimální řešení pro tento problém algoritmem s časem běhu f(k)n, kde f je vyčíslitelná funkce a k je tree-depth n vrcholového grafu na vstupu. Naopak takovýto algoritmus nemůže existovat pro parametr tree-width (pokud FPT ̸= W[1]). V současné době je jen velmi málo známých problémů s touto vlastností....
|
|
|
Obtížné problémy vzhledem k parametru různorodost sousedství
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Fiala, Jiří (oponent)
Parametrizovaná složitost je oblast teoretié informatiky zabývající se výpočetní složitostí pro- blémů měřenou nikoliv pouze délkou vstupu, ale i nějakým jeho parametrem. "Různorodost soused- ství" je nový strukturální parametr grafu, který je atraktivní především proto, že pro grafy s pevnou různorodostí sousedství se stávají efektivně řešitelnými i některé problémy, jež zůstávají těžké pro jiné parametry s různorodostí sousedství neporovnatelnými. V této práci nově ukazujeme efektivní řeši- telnost vzhledem k různorodosti sousedství pro tři problémy těžké vzhledem ke stromové šířce. To tvoří hlavní část této práce a jedná se o náš vlastní výzkum. Dále pak práce obsahuje přehled další zajímavý problémů a také shrnutí současného stavu v oblasti parametrů pro řídké a husté grafy. 1
|
|
|
Výpočetní složitost v teorii grafů
Doucha, Martin ; Kratochvíl, Jan (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Tato práce zavádí dvě nové parametrizace grafových úloh zobecňující vrcholové pokrytí, které v hierarchii grafových parametrizací vyplňují část prostoru mezi vrcholovým pokrytím a klikovou šířkou. Dále zde zkoumáme parametrizovanou složitost hledání Hamiltonovské cesty a kružnice, klasického barvení grafu, problému Precoloring extension a Equitable coloring pro tyto nové parametrizace. Kromě problému Precoloring extension, který je pro jednu parametrizaci W[1]-těžký, se pro všechny ostatní problémy podařilo najít FPT algoritmus pro obě parametrizace. Hranici mezi třídami FPT a W[1] se tak u těchto problémů podařilo posunout blíže směrem k parametrizaci klikovou šířkou.
|
|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (vedoucí práce) ; Telle, Jan Arne (oponent) ; Obdržálek, Jan (oponent)
Název práce: Parametrizovaná složitost Autor: Ondřej Suchý Katedra (ústav): Katedra aplikované matematiky Školitel: Prof. RNDr. Jan Kratochvíl, CSc. e-mail školitele: honza@kam.mff.cuni.cz Abstrakt: Tato práce se zabývá parametrizovanou složitostí NP-těžkých grafo- vých problémů. Zkoumáme složitost problémů v různých scénářích, vzhle- dem k rozličným parametrům a jejich kombinacím. Naším cílem je spíše rozlišit v tomto mnohorozměrném smyslu, zda daný parametr dělá problém parametrizovaně dostupným, nebo nedostupným, než představit algorit- mus, který dosahuje nejlepší možné časové složitosti. V otázkách, které studujeme, je typicky parametr první volby neúspěšný a tak využíváme méně standardních parametrů. První zkoumaná množina problémů je společným zobecněním mnoha dobře známých a prostudovaných problémů dominance a nezávislosti. Navrhu- jeme zde použít duální parametrizaci a ukážeme, že narozdíl od standardní parametrizace velikostí řešení, tato parametrizace dokáže ohrančit nevyh- nutelnou kombinatorickou explozi. Další studované problémy jsou analogií Steinerova problému v orientovaných grafech. Parametrizace pomocí počtu terminalů se jeví jako dříve neprobádaná alternativa v...
|
host ::
RSS.